2021/06/29 更新:添加了详细的推式子过程,以及修改了排版。
如果有人问我推过最恶心的式子是哪个,我会说是这题。
我就不打表找规律,推式子警告
我们设 f(n,k,x) 表示有 n 个人的情况下,第 k 小的红包钱数大于 x 的概率。这也等价于至少 n−k+1 个红包的钱数大于 x 的概率。这里推荐使用第二种定义,方便理解后面的递推边界。
那么,容易看出我们要求的答案 ans(n,k)=∫01f(n,k,x)dx。
考虑 f 的递推式,n 个人时生成了 n−1 个随机数,设这些随机数里最小的那个是 v。此时一定有一个金额为 v 的红包,讨论 v 和 x 的大小关系:
如果 v<x,那么剩下 n−1 个红包里就需要 n−k+1 个红包大于 x;
如果 v>x,那么剩下 n−1 个红包里就需要 n−k 个红包大于 x。
再想想,“1−v 块钱分成 n−1 个红包有 n−k+1 个红包大于 x”和“1 块钱分成 n−1 个红包有 n−k+1 个红包大于 1−vx”是一样的,可以理解为通货膨胀了(?)
还有一个问题,虽然随机数是均匀分布的,但 n−1 个随机数中的最小值 v 可不是均匀分布的。我们要求出这个最小值小于 v 的概率是 1−(1−v)n−1,然后对它求导得到 (n−1)(1−v)n−2,这个可以认为是最小值为 v 的相对概率
综合上述讨论,可以得到 f 的递推式
=+f(n,k,x)(n−1)∫0x(1−v)n−2f(n−1,k−1,1−vx)dv(n−1)∫x1(1−v)n−2f(n−1,k,1−vx)dv
开始积分
=+∫01f(n,k,x)dx(n−1)∫01∫0x(1−v)n−2f(n−1,k−1,1−vx)dvdx(n−1)∫01∫x1(1−v)n−2f(n−1,k,1−vx)dvdx
设 t=1−vx 然后化简一波,此处省略去了漫长的计算过程
=+∫01f(n,k,x)dxnn−1∫0+∞(1−(t+1)n1)f(n−1,k−1,t)dtnn−1∫0+∞(t+1)n1f(n−1,k−1,t)dt
注意这里积分上界变成了 +∞,不是 1,因为 t 的范围可以到正无穷大,而且当 k=n+1,x>1 时 f(n,k,x) 仍然有意义且值为 1,所以一定要积到正无穷大!下面推边界的时候也有这方面的说明
貌似得到了更复杂的式子,出现了 (t+1)n1 这个因子,我们用同样的方法继续积分看看
=+∫0+∞(x+1)(n+1)1f(n,k,x)dxnn−1∫0+∞((t+1)n1−(2t+1)n1)f(n−1,k−1,t)dtnn−1∫0+∞(2t+1)n1f(n−1,k−1,t)dt
事情逐渐清晰起来,可以猜想并证明:
=+∫0+∞(lx+1)(n+1)1f(n,k,x)dxnn−1∫0+∞((lt+1)n1−((l+1)t+1)n1)f(n−1,k−1,t)dtnn−1∫0+∞((l+1)t+1)n1f(n−1,k−1,t)dt
这回可以递推了。设
P(n,k,l)=∫0+∞(lx+1)(n+1)1f(n,k,x)dx
则有
P(n,k,l)=nn−1(P(n−1,k−1,l)−P(n−1,k−1,l+1)+P(n−1,k,l+1))
递推边界通过 P 和 f 的定义可以计算:
P(n,k,l)=⎩⎪⎨⎪⎧0,∫0+∞(lx+1)−n−1dx=ln1,∫01(lx+1)−2dx=l+11,k=0;k=n+1;n=1;
这里为什么 n=1 时积到 1 而 k=n+1 时要积到 +∞ 呢,因为 x>1 时 f(1,1,x)=0,但是 k=n+1 时 f(n,k,x) 表示的是至少 0 个红包大于 x 的概率,那么无论 x 为何值 f(n,k,x) 的值都为 1
最终答案就是 P(n,k,0)。
那么这玩意怎么化简呢
首先我们看着 nn−1 这个因子很难受,不妨修改一下 P 的定义,用 P(n,k,l) 表示之前 nP(n,k,l) 表示的意思,那么递推式和边界都要修改,顺便还能把递推式改为等价的更简洁的形式
P(n,k,l)=⎩⎪⎨⎪⎧0,l1,P(n−1,k−1,l)−P(n−1,k−1,l+1)+P(n−1,k,l+1),n=0,k≤0;n=0,k>0;n>0
此时 ans(n,k)=n1P(n,k,0)。
假设从 P(n,k,0) 递归到 n=0 共调用了 a 次 P(n−1,k−1,l) 分支,b 次 P(n−1,k−1,l+1) 分支,c 次 P(n−1,k,l+1) 分支。需要满足 a+b+c=n,a+b<k。那么这部分的贡献就是 a!b!c!(b+c)n!(−1)b,总和为
P(n,k,0)=a+b+c=n,a+b<k∑a!b!c!(b+c)n!(−1)b
继续化简
P(n,k,0)========a+b+c=n,a+b<k∑a!b!c!(b+c)n!(−1)ba=0∑k−1a!(n−a)n!b=0∑k−a−1(−1)bb!(n−a−b)!1a=0∑k−1a!(n−a)!(n−a)n!(−1)k−a−1C(n−a−1,k−a−1)(n−k)!n!a=0∑k−1(n−a)2a!(k−a−1)!(−1)k−a−1(n−k)!n!(k−1)!1a=0∑k−1(−1)k−a−1C(k−1,a)(a−n)−2(n−k)!n!(k−1)!1a=0∑k−1(−1)k−a−1C(k−1,a)j=0∑∞C(−2,j)aj(−n)−2−j(n−k)!n!j=0∑∞C(−2,j)(−n)−2−j(k−1)!1a=0∑k−1(−1)k−a−1C(k−1,a)aj(n−k)!n!j=0∑∞(j+1)n−2−jS2(j,k−1)
记 Gm(x) 是第二类斯特林数第 m 列的普通生成函数,Gm′(x) 为其导数。我们有:
Gm(x)=i=0∑∞S2(i,m)xi=j=1∏m1−jxx
Gm′(x)=j=1∑mx(1−jx)1Gm(x)
原式可以写成生成函数的形式:
P(n,k,0)=====(n−k)!n!j=0∑∞(j+1)n−2−jS2(j,k−1)(n−k)!n!(n−3Gk−1′(n1)+n−2Gk−1(n1))(n−k)!n!n−2(1+j=1∑k−1n−jn)Gk−1(n1)(n−k)!n!n−1(l=n−k+1∑nl1)j=1∏k−1n−j1l=n−k+1∑nl1
这回可以快速计算多组询问了。别忘了除以 n!!
ans(n,k)=n1l=n−k+1∑nl1
提醒:比赛时遇到这种题果断打表找规律。